/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/

/*  BiteStream
    **********
    rennex@iki.fi


    Introduction
    ------------
    BiteStream is a binary transport encoding that was developed to replace
    the cumbersome XML format used earlier. Using XML for transmitting sensor
    readings in real time is like killing a fly with a cannon. The plaintext
    XML isn't well suited for binary data, and there is no need for the
    transmissions to be human-readable.
    
    Data encoded with BiteStream is simply a compact chunk of binary data.
    Both encoding and decoding use very little processor time, and the data
    overhead is minimal as well. Basically the stream is an ordered series
    of key-value pairs, where the key is either a 24-bit integer or a string
    up to 254 characters long, and the value is a chunk of binary data from
    1 byte up to 1 gigabyte in length. BiteStream is lightweight enough to be
    a good choice in a vast range of cases where flexible data structures
    need to be serialized - the number of data items and the length of each
    item may vary freely.


    Author's notes
    --------------
    When constructing a BiteStream, the programmer doesn't need to know the
    total length of the data he is planning to include. The functions used to
    append tags to the stream check if enough memory has been allocated; if
    not, the buffer is realloc()'d bigger. That may consume some time, so the
    bsClear() function may be handy: it empties the stream but leaves the old
    buffer intact, so if it was previously enlarged, you can save some
    realloc()s.
    
    It may also happen that the programmer knows how much data a tag will
    contain, but hasn't computed the data yet. Instead of allocating memory
    for it, building it, then handing it over to be copied to the stream,
    he may add a tag with a NULL data pointer. In that case, memory is
    allocated in the stream but no data is copied. The bsAdd*() functions
    will return a pointer to the location of that chunk in the stream, so the
    programmer may construct the data in-place, directly inside the stream.
    
    A stream must be finalized by calling bsFinalize(), before saving or
    transmitting the stream buffer. This will append the end marker and
    write the stream header, for which space has been reserved right from
    the start.
    
    You "open" the serialized stream by calling bsDecode(), and then iterate
    over the tags by calling bsNextTag(). You may return back to the first
    tag by calling bsRewind(). Note that you must not free the memory passed
    to bsDecode() until you are done decoding it. Calling bsFree() on a
    decoded BiteStream will not free the buffer that was passed to it.

    Modifying decoded streams has not been disabled, but it is strongly
    discouraged. It is only safe to modify the data in-place. Adding, removing
    or resizing tags is impossible. To call bsClear() on it and then adding
    tags would be madness. Madness, I tells ya!

    BiteStream should fully work in a 64-bit environment (as long as int is
    32 bits), but adding tags longer than 1 GB or making a stream over 4GB in
    length is impossible.



    The serialized format of BiteStream is quite straightforward. The first
    12 bytes contain a bsStreamHeader, which contains an identifying value
    ("BiTE" as a 32-bit integer), the number of tags in the stream (here "tag"
    refers to key-value pairs or just the key itself), and the total length
    in bytes. Unfortunately there is no version information or flags; those
    could be added as an extra tag in the beginning of the stream with a
    reserved tag value (<100). Programs decoding the stream are supposed to
    skip any unknown keys (although it's not mandated, it's only common sense
    for future compatibility).

    The very next byte is the start of the first tag. Here is a diagram of a
    tag's structure:
    
        Regular tag:
    
            length
            |key
            ||  data->
            ||  |
            LKKKDDDDD...

        Long tag: (over 255 bytes long)

            null byte
            |length (2 to 4 bytes)
            ||  key
            ||  |  data->
            ||  |  |
            0LLLKKKDDDDD...

        Named tag:

            length (may be as in a long tag described above)
            |key = BS_NAMED
            ||  name length (including terminating zero)
            ||  |name
            ||  ||   null byte
            ||  ||   |data->
            ||  ||   ||
            LKKKlNNNN0DDDDD...

    The first byte of each tag tells its data length. That is unless the byte
    is 0, in which case the two highest bits of the next byte indicate how
    many more bytes are included in the length (1 to 3, plus the six lowest
    bits of first byte). If those two bits are both zero, this tag is the end
    marker of the entire stream and no further bytes may be accessed without
    risking a segmentation fault. The length is saved in big endian notation
    (MSB first). Note that the length only includes the payload data and the
    tag name (with terminating zero), i.e. not the key or any of the bytes
    that indicate lengths. That may seem silly, but as you can see in the
    code, it all turns out quite nicely. [In hindsight, the variable-sized
    length field is unnecessary complexity. It could just as well be 1 byte 
    for short tags and 1+4 bytes for longer ones, because what's another 2
    bytes overhead when the data is from 256 bytes to 64 kB long?]

    After the length comes 3 bytes containing the 24-bit key, again in big
    endian. The next byte is the first byte of the payload data, unless the
    key was BS_NAMED, in which case that byte tells the length of the tag name
    including the trailing zero, and the payload will follow right after that.
    
    The entire stream is terminated with two zero bytes, which will look like
    a zero-length tag to the reader/decoder function.

    Note that the struct BiteStream is NOT the same as the bsStreamHeader
    that's inserted in the beginning of the stream.

*/

#include <malloc.h>
#include <string.h>
#include <stdio.h>

#include "bitestream.h"


// Allocates and initializes an empty BiteStream.
BiteStream *bsAlloc(void) {
    BiteStream *s = (BiteStream *) malloc(sizeof(BiteStream));
    if (s) {
        s->bufsize = BS_BUFLEN;
        s->buf = (char *) malloc(s->bufsize);
        if (!s->buf) {
            free(s);
            return 0;
        }

        bsClear(s);
    }

    return s;
}


// Clears the tags in a BiteStream, allowing reuse of the data buffer
void bsClear(BiteStream *s) {
    // reserve space for the header and clear it
    s->length = sizeof(bsStreamHeader);
    memset(s->buf, 0, sizeof(bsStreamHeader));
    
    s->numtags = 0;
    s->flags = 0;
    s->pos = 0;
}


// Frees the memory occupied by a BiteStream and its storage.
// If the BiteStream was returned by bsDecode(), the buffer
// supplied to it WILL NOT be freed.
void bsFree(BiteStream *s) {
    if (!(s->flags & BSF_DONTFREEBUF)) free(s->buf);
    free(s);
}


// allocates more memory if the buffer can't hold "length" more bytes
static void ensurebuffer(BiteStream *s, int length) {
    // need more space in the buffer?
    if (s->bufsize - s->length < length) {
        /* // for arbitrary-sized increments, instead of 2^n
        int need = length + s->length - 1;
        s->bufsize = need+increment - need%increment;
        */
        // this adds n*BS_BUFLEN to the length, keeping n as low as possible
        s->bufsize += (length - (s->bufsize - s->length) + BS_BUFLEN-1) & -BS_BUFLEN;
        s->buf = (char *) realloc(s->buf, s->bufsize);
        //printf("Allocated more memory, buffer is now %d bytes.\n", s->bufsize);
    }
}



// Finalizes a BiteStream for sending over a socket or writing to file.
// You can proceed to write s->length bytes from s->buf.
void bsFinalize(BiteStream *s) {
    bsStreamHeader *hdr;

    // ensure room for 2 null bytes (the end marker)
    ensurebuffer(s, 2);
    s->buf[s->length++] = 0;
    s->buf[s->length++] = 0;

    hdr = (bsStreamHeader *) s->buf;
    hdr->magic = BS_MAGIC;
    hdr->numtags = s->numtags;
    hdr->length = s->length;
}


// "Decodes" a BiteStream read from a socket or file. In practice,
// attaches the supplied data buffer as the bitestream's storage.
// Appending more tags to it is discouraged, and is possible ONLY if
// buf can be realloc()ed (the exact pointer was returned by malloc())!

// Returns NULL if the data isn't a proper, finalized stream.
BiteStream *bsDecode(char *buf) {
    BiteStream *s;
    bsStreamHeader *hdr;

    hdr = (bsStreamHeader *) buf;
    if (hdr->magic != BS_MAGIC) return 0;

    s = (BiteStream *) malloc(sizeof(BiteStream));

    if (s) {
        s->numtags = hdr->numtags;
        s->length = hdr->length - 2;
        s->bufsize = hdr->length;
        s->flags = BSF_DONTFREEBUF;
        s->buf = buf;
        bsRewind(s);
    }

    return s;
}



// Examines a BiteStream and prints the findings into stderr.
// Intended for debugging purposes.
void bsDump(char *buf) {
    unsigned int firstbytes;
    BiteStream *s;
    int i;

    if (!buf) {
        fprintf(stderr, "Error: pointer is NULL!\n");
        return;
    }

    firstbytes = ((bsStreamHeader *) buf)->magic;
    if (firstbytes != BS_MAGIC) {
        unsigned char *c = (unsigned char *) buf;

        fprintf(stderr, "Error: the first 4 bytes are 0x%02x%02x%02x%02x, was expecting 0x%02x%02x%02x%02x.\n",
                c[0], c[1], c[2], c[3], BS_MAGIC & 0xff, (BS_MAGIC>>8) & 0xff, (BS_MAGIC>>16) & 0xff, (BS_MAGIC>>24) & 0xff);

        if (firstbytes) fprintf(stderr, "This probably means the pointer points to the wrong data.\n");
        else fprintf(stderr, "This happes if the BiteStream wasn't finalized by the sender,\n"
                             "or it may be an invalid pointer.\n");
        return;
    }

    s = bsDecode(buf);
    if (!s) {
        fprintf(stderr, "Out of memory! Unpossible!\n");
        return;
    }

    fprintf(stderr, "Valid-looking BiteStream found. It seems to be %d bytes long and to have %d tags.\n",
            s->bufsize, s->numtags);
    
    for (i = 0; i < s->numtags; i++) {
        int k;
        bsTag *t;
        
        t = bsNextTag(s);
        if (t->tag == BS_NAMED) fprintf(stderr, "#%d: tag \"%s\" =", i, t->name);
        else fprintf(stderr, "#%d: tag %u (0x%08x) =", i, t->tag, t->tag);

        for (k = 0; k < t->length; k++) {
            fprintf(stderr, k % 4 == 0 ? " %02x" : "%02x", (unsigned char) t->string[k]);
            if (k >= 20) {
                fprintf(stderr, "...");
                break;
            }
        }

        fprintf(stderr, "\n");
    }

    if (!bsNextTag(s)) {
        fprintf(stderr, "Stream ended after %d tags like was expected.\n", i);
    }
    else {
        fprintf(stderr, "Warning: stream didn't end cleanly, seems the end marker is missing!\n");
    }
    
    fprintf(stderr, "Dump finished.\n");
    
}
        





// Gets the next tag in the stream. Returns a pointer to
// s->tag, or NULL if there are no more tags.
bsTag *bsNextTag(BiteStream *s) {
    bsTag *bt = &s->tag;
    unsigned char *p = (unsigned char *) s->pos;
    int len = *p++;

    if (len == 0) {
        unsigned char x, n;

        x = *p++;
        len = x & 0x3f;
        n = x >> 6;
        // last tag in the stream?
        if (n == 0) return 0;

        while (n--) {
            len = (len << 8) | *p++;
        }
    }


    bt->tag = *p++ << 16;
    bt->tag |= *p++ << 8;
    bt->tag |= *p++;

    // named tag?
    if (bt->tag == BS_NAMED) {
        unsigned char namelen = *p++;
        bt->name = (char *) p;
        p += namelen;
        len -= namelen;
    }
    else {
        bt->name = 0;
    }

    if (len == 4) bt->value = *(int *) p;
    else bt->value = 0;

    bt->length = len;
    bt->string = (char *) p;
    bt->data = p;

    s->pos = (char *) p + len;

    return bt;

}


// Resets the BiteStream's read position to the first tag.
void bsRewind(BiteStream *s) {
    s->pos = s->buf + sizeof(bsStreamHeader);
}


// internal: adds binary data as a numbered or named tag
static char * _addbin(BiteStream *s, int tag, const char *name, const void *data, int length) {
    unsigned char *p;
    int namelen = 0;

    if (length <= 0) return 0;          // invalid packet length


    if (tag == BS_NAMED) {
        if (!name) return 0;            // error: no tag number or name
        namelen = strlen(name)+1;
        if (namelen > 0xff) return 0;   // tag name too long
        length += namelen;
    }

    // make sure there's enough space for the data and tag (and name)
    ensurebuffer(s, length+9);
    p = (unsigned char *) s->buf + s->length;

    // write this item's length (incl. tag name) to the stream
    if (length <= 0xff) {
        *p++ = length;
    }
    else {
        unsigned char *len = (unsigned char *) &length;

        *p++ = 0;

        // zomg, this looks ugly. But it's very clever, I assure you!
        if (length <= 0x00003fff) {
            *p++ = 0x40 | len[1];
            *p++ = len[0];
        }
        else
        if (length <= 0x003fffff) {
            *p++ = 0x80 | len[2];
            *p++ = len[1];
            *p++ = len[0];
        }
        else
        if (length <= 0x3fffffff) {
            *p++ = 0xc0 | len[3];
            *p++ = len[2];
            *p++ = len[1];
            *p++ = len[0];
        }
        else return 0;                  // packet too long
    }

    // write the tag to the stream
    *p++ = (tag >> 16) & 0xff;
    *p++ = (tag >> 8) & 0xff;
    *p++ = tag & 0xff;

    if (tag == BS_NAMED) {
        // write the tag name to the stream
        *p++ = namelen;
        memcpy(p, name, namelen);
        p += namelen;
        length -= namelen;
    }

    // write the data
    if (data) memcpy(p, data, length);

    s->length = p - ((unsigned char *) s->buf) + length;
    s->numtags++;

    return (char *) p;
}


// Appends an int-type tag to the stream.
char *bsAddInt(BiteStream *s, int tag, int value) {
    return _addbin(s, tag, 0, &value, sizeof(int));
}

// more primitive types
char *bsAddFloat(BiteStream *s, int tag, float value) {
    return _addbin(s, tag, 0, &value, sizeof(float));
}
char *bsAddDouble(BiteStream *s, int tag, double value) {
    return _addbin(s, tag, 0, &value, sizeof(double));
}


// Appends a null-terminated string-type tag to the stream.
char *bsAddStr(BiteStream *s, int tag, const char *string) {
    return _addbin(s, tag, 0, string, strlen(string)+1);
}


// Appends a binary data block-type tag to the stream.
// The data pointer may be NULL, in which case space is
// reserved in the stream and you can fill in the data later.
// The minimum length is 1 byte, maximum 1073741823.
// Returns a pointer to the data in the stream (use this if
// you want to fill in the data later).
char *bsAddBin(BiteStream *s, int tag, const void *data, int length) {
    return _addbin(s, tag, 0, data, length);
}


// --- named tag versions ---

char *bsAddNamedInt(BiteStream *s, const char *name, int value) {
    return _addbin(s, BS_NAMED, name, &value, sizeof(int));
}

char *bsAddNamedFloat(BiteStream *s, const char *name, float value) {
    return _addbin(s, BS_NAMED, name, &value, sizeof(float));
}
char *bsAddNamedDouble(BiteStream *s, const char *name, double value) {
    return _addbin(s, BS_NAMED, name, &value, sizeof(double));
}


char *bsAddNamedStr(BiteStream *s, const char *name, const char *string) {
    return _addbin(s, BS_NAMED, name, string, strlen(string)+1);
}


char *bsAddNamedBin(BiteStream *s, const char *name, const void *data, int length) {
    return _addbin(s, BS_NAMED, name, data, length);
}







